package leetcode_81_100;

import utils.ListNode;

import java.util.ArrayList;
import java.util.List;

public class restoreIpAddresses_93 {
    /**
     * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址
     * 这些地址可以通过在 s 中插入 '.' 来形成。
     * 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        /**
         * 这种不定状态的结果集还是要递归回溯
         * 1ms  96%,但是太繁琐了
         */
        List<String>ans=new ArrayList<>();
        // 如果长度不够，不搜索
        if (s.length() < 4 ||s.length() > 12) {
            return ans;
        }
        function(s,0,ans,new StringBuilder(),new StringBuilder(),false,0);
        return ans;
    }

    /**
     * 递归
     * @param s 字符串
     * @param index 当前位置
     * @param ans 结果集
     * @param num 当前组成的数字
     * @param ip 实时组成的ip
     * @param isAdd 是否在这层递归中添加num进ip中
     * @param count ip中数字的个数
     */
    void function(String s,int index,List<String>ans,StringBuilder num,StringBuilder ip,boolean isAdd,int count){
        if (isAdd){       //上一层要求时,必须更换数字
            if(ip.length()!=0)
                  ip.append(".");
            ip.append(num);
            if (index == s.length() && count == 4) {   //全部遍历完，正好满足ip格式
                ans.add(ip.toString());
                return;
            }
            if(count==4&&index!=s.length() || index==s.length()&&count<4 ) //字符没使用完结果就够了或者结果不够四个，字符已经用完都直接返回
                return ;
            function(s,index,ans,new StringBuilder(),ip,false,count); //更换一个空的num，index不变
        }else { //没有特殊情况

            if (index == s.length())return;
            num.append(s.charAt(index++));//一个数字
            function(s,index,ans,num,ip,true,count+1);
            //ip回退两个字符
            if(index==1)ip.deleteCharAt(0);
            else ip.delete(ip.length()-2,ip.length());
           //单个数字等于0，下边就不能以0开头添加字符
            if(s.charAt(index-1)-'0' == 0)
                return;

            if (index==s.length())return;
            num.append(s.charAt(index++));//两个数字
            function(s,index,ans,num,ip,true,count+1);
            //回退三个字符
            if(index==2)ip.delete(0,2);
            else ip.delete(ip.length()-3,ip.length());

            if (index==s.length())return;
            num.append(s.charAt(index++));//三个数字
            // 数字小于等于255
            if (Integer.parseInt(num.toString()) <= 255) {
                function(s, index, ans, num, ip, true, count+1);
                //回退四个字符
                if(index==3)ip.delete(0,3);
                else ip.delete(ip.length() - 4, ip.length());
            }
        }
    }
}
